1. Field of the Invention
This invention relates generally to a multifunctional printing system with one or more queues and, more particularly, to a job contention management architecture which manages the printing system""s resources to enable a service to process a job for multiple video capabilities using commonly shared resources.
2. Brief Description of Earlier Developments
Electronic printing systems typically include an input section, sometimes referred to as an input image terminal (xe2x80x9cIITxe2x80x9d), a controller, and an output section or print engine, sometimes referred to as an image output terminal (xe2x80x9cIOTxe2x80x9d). In one type of electronic printing system, manufactured by Xerox(copyright) Corporation, known as the DocuTech(copyright) electronic printing system, a job can be inputted to the printing system from, among other sources, a network or a scanner. An example of a printing system with both network and scanner inputs is found in the following patent:
U.S. Pat. No. 5,170,340
Patentees: Prokop et al.
Issued: Dec. 8, 1992
When a scanner is employed to generate the job, image bearing documents are scanned so that the images therein are converted to image data for use in making prints. When a network is used to generate the job, a stream of data, including various job related instructions and image data, expressed in terms of a page description language is captured, decomposed and stored for printing. As is known, a network job can have its origin in a remote client, such as a workstation, or a print server with a storage device. Jobs provided at the IIT may be stored in a memory section, sometimes referred to as xe2x80x9celectronic precollation memoryxe2x80x9d. An example of electronic precollation memory may be found in the following patent:
U.S. Pat. No. 5,047,955
Patentees: Shope et al.
Issued: Sep. 10, 1991
U.S. Pat. No. 5,047,955 discloses a system in which input image data of a job is rasterized and compressed. The compressed, rasterized image data is then stored, in collated form, in a job image buffer. Once the job has been stored in the job image buffer, a selected number of job copies can be decompressed and printed without further job rasterization.
In one area related to electronic printing, namely digital copying, a demand for xe2x80x9cmultifunctionalityxe2x80x9d continues to grow. As illustrated by the following patent, a multifunctional digital copier can assume the form of an arrangement in which a single electrostatic processing printer is coupled with a plurality of different image input devices, with such devices being adapted to produce image related information for use by the printer.
U.S. Pat. No. 3,957,071
Patentee: Jones
Issued: Jul. 27, 1971
U.S. Pat. No. 3,957,071 discloses that the image related information, in one example, could have its origin in video facsimile signals, microfilm, data processing information, light scanning platens for full size documents, aperture cards and microfiche.
The following patents also relate to the area of multifunctional digital copying:
U.S. Pat. No. 4,821,107
Patentees: Naito et al.
Issued: Apr. 11, 1989
U.S. Pat. No. 5,021,892
Patentees: Kita et al.
Issued: Jun. 4, 1991
U.S. Pat. No. 5,175,633
Patentees: Saito et al.
Issued: Dec. 29, 1992
U.S. Pat. No. 5,223,948
Patentees: Sakurai et al.
Issued: Jun. 29, 1993
U.S. Pat. No. 5,276,799
Patentee: Rivshin
Issued: Jan. 4, 1994
U.S. Pat. No. 5,307,458
Patentees: Freiburg et al.
Issued: Apr. 26, 1994
Multifunctional copying devices are typically adapted to store a plurality of jobs for eventual printing. In one example, jobs are ordered for printing in an arrangement referred to as a xe2x80x9cprint queuexe2x80x9d. Xerox Network Systems have employed the concept of the print queue for at least a decade to manage jobs at network printers. Further teaching regarding network printing is provided in the following patent:
U.S. Pat. No. 5,436,730
Patentee: Hube
Issued: Jul. 25, 1995
The concept of a print queue is integral to the operation of various digital reproduction systems. Through appropriate queue management, a job currently in the process of being printed can be interrupted with an interrupt job in a manner disclosed by the following:
U.S. Pat. No. 5,206,735
Patentees: Gauronski et al.
Issued: Apr. 27, 1993
Referring particularly to the ""735 Patent, a special job is obtained from a mass memory, shown by way of a xe2x80x9cjob filexe2x80x9d, and inserted into the queue at a xe2x80x9clogical pointxe2x80x9d with respect to the job currently being processed. When printing reaches the logical point at which the special job was inserted, the job currently being processed is interrupted so that the special job is processed. Upon completion of the processing of the special job, processing of the interrupted job is resumed. The queue disclosed in the ""735 Patent is managed, in the normal case, on a first-come-first-serve (xe2x80x9cFIFOxe2x80x9d) basis except when special or interrupt jobs are inserted into the queue. In the illustrated embodiment of the ""735 Patent, the interrupt job is inserted into the queue as described above except when an interrupt job is currently in the process of printing. When an interrupt job is currently printing, a second interrupt job is placed behind the interrupt job in process. Essentially, priority is given to the interrupt job currently in process. The concerns associated with interrupting a first interrupt job with a second interrupt job are also addressed in the following patent:
U.S. Pat. No. 5,535,009
Patentee: Hansen
Issued: Jul. 9, 1996
The queue management arrangement of the ""735 Patent is not optimally suited for use in a multifunctional context because it does not differentiate among job types for the purpose of managing the queue. Consequently, a print job cannot, in many common instances, be given priority over a copy job, or vice versa. Systems particularly well suited for use with a multifunctional printing systems are disclosed by the following references:
U.S. Pat. No. 4,947,345
Patentees: Paradise et at.
Issued: Aug. 7, 1990
Japanese Application 58-152821
Published: Aug. 22, 1983
Referring particularly to the ""345 Patent, a first queue is used to store copy and print jobs, while a second queue, communicating with the first queue, is used to store facsimile (xe2x80x9cfaxxe2x80x9d) jobs in parallel with the first queue. After a pre-selected number of one or more fax jobs is stored in the second queue, the stored job(s) is placed in front of the jobs of the first queue so that the one or more fax jobs can be printed ahead of the currently queued copy/print jobs. While the queue management scheme of the ""345 Patent accommodates for job differentiation, it only does so in a limited manner. For instance, the fax queue can be given preferential treatment relative to the copy/print queue, so that one or more fax jobs can be printed ahead of a copy or print jobs. No mechanism for treating a given copy or print job preferentially, however, is suggested. Even though U.S. Pat. No. 5,511,150 to Beaudet et al. (Issued Apr. 23, 1996) accommodates for preferential treatment of copy jobs relative to print jobs, it does not do so in a queue context as discussed in the references above. Additionally, in the approach of the ""345 Patent, a copy or print job can get xe2x80x9cstuckxe2x80x9d in the copy/print job queue when multiple fax jobs are given preferential processing treatment relative to the copy/print jobs
U.S. Pat. No. 5,113,355
Patentee: Nomura
Issued: May 12, 1992
Referring to the 355 patent, it discloses a printer control system for enabling queue identifiers, which identify different print jobs, to be sorted such that those queue identifiers identifying print jobs which require fonts that are already loaded in the print server are placed at the head of a print list, and those queue identifiers identifying print jobs which require fonts that are not loaded in the print server are placed at the end of the print list. The print jobs are then processed in the order that the queue identifiers appear on the print list. When a print job to be processed requires fonts that are not loaded into the system a message is displayed on a display unit in order to inform the operator which fonts need to be loaded into the system.
U.S. Pat. No. 5,327,526
Patentee: Nomura et al.
Issued: Jul. 4, 1994
Referring to the 526 patent it discloses a print job control system which processes print requests to set an order of priority for printing print jobs. A print job manager checks the print request and determines what print option is selected and manipulates the queue identifiers associated with respective print jobs and enters them into a print queue table. One feature allows changing the print order thereby overriding the designated print option. Another feature allows for increasing the priority of low priority jobs regardless of the designated print option assuring that the low priority jobs will be printed.
U.S. Pat. No. 5,377,016
Patentee: Kashiwagi et al.
Issued: Dec. 27, 1994
Referring to the 016 patent there is disclosed a control circuit which receives advance data representing a predetermined number of copy jobs to be provided from a scanner and data representing a predetermined number of print jobs to be provided from external equipment. The control circuit causes each of the copy jobs and print jobs on the basis of such data to be queued, and the jobs to be processed in a time divisional and parallel manner. Basically, the control circuit gives higher priority to the copy job. The priority order can be changed according to an instruction from a user interface. When a current job has been suspended, the control circuit causes a succeeding job to be processed earlier.
U.S. Pat. No. 5,923,826
Patentee: Grzenda et al.
Issued: Jul. 13, 1999
Referring to the 826 patent there is disclosed a printing system comprising a digital reproduction system communicating with a remote document processing station by way of a print server. The printing system includes a first queue of first jobs to be executed with the digital reproduction system maintained at the print server and a second queue of second jobs to be executed with the digital reproduction system maintained at the digital reproduction system. The printing system further includes a queue process communicating with both the first and second queues for forming a composite queue to reflect an order in which the first and second jobs of the first queue and the second queues are to be executed with the digital reproduction system. A representation of the composite queue is then displayed at a user interface disposed at the remote document processing station.
U.S. application Ser. No. 09/015,144
Applicant: Salgado et al.
Pending
A method is provided for a multifunctional printing system in which a first job, developed at a first service, and a second job, developed at a second service are placed in a queue for processing. A first value is assigned to the first job and a second value is assigned to the second job, with the first and second values varying in magnitude as a function of the first and second services. In one example, the first job is placed in the queue and a portion thereof is processed. Subsequently, the second job is placed in the queue and processing of the first job is interrupted by the second job if the second value is greater in magnitude than the first value.
The aforenoted queuing approaches, while well intended for their limited purposes, lack the sort of efficient queue management that is required to make multifunctional printing systems having shared resources fully productive. Multifunction printing system""s capabilities and uses are expanding at an ever-increasing rate. It is desirable to provide a multifunctional printing system that gives improved productivity by utilizing queue management at the capability and resource sub-job levels in order to maximize the productivity of the system. At the same time, it is desirable to provide a queue management system for a multifunctional printing system facilitating the efficient thruput of all types of jobs which might be encountered by the multifunctional printing system.
The Xerox Corporation Digital Copier Multifunction Systems comprising the DC 240 ST and the DC 265 ST include a Job Contention Manager which provides queue management at the Basic Job Service level. This approach has the ability to concurrently process sub-jobs which do not conflict at the basic resource level. For example, a scan sub-job and a mark sub-job can be carried out concurrently, however, all the capabilities associated with each basic resource for the sub-job are tied up until the sub-job is completed.
A more productive approach as disclosed in U.S. patent application Ser. No. 09/450,146, to Salgado et al., entitled METHOD AND APPARATUS FOR MANAGING JOB CONTENTION FOR SYSTEM RESOURCES IN AN ELECTRONIC REPROGRAPHIC SYSTEM, filed of even date herewith, releases capabilities to other sub-jobs when they are not being used or are required by higher priority sub-jobs. This is accomplished by providing job contention management at the lower level of capability job requests with both capability resource queues and basic resource queues. The present invention extends this prioritization approach to enable a job service to process a sub-job for multiple video capabilities.
The disclosure of each patent or application mentioned or discussed in the above Background is incorporated herein by reference.
In accordance with the presently disclosed invention there is provided a method and apparatus for prioritizing the use of multifunctional printing system""s basic processing resources to enable a job service to process a sub-job to provide improved system concurrency using commonly shared resources and thus streamlining the process. Improved performance and efficiency in processing jobs is provided by the early freeing up of video resources resulting from the process and apparatus of this invention. It provides the ability to perform more efficient job processing by a job service.
In accordance with a preferred aspect of this invention, the printing system employs a controller with an improved job contention manager (JCM). The process in accordance with a preferred embodiment of the invention comprises providing each of a plurality of basic resources of the printing system with a queue. One or more job services, at desired times, signals the JCM to carry out a sub-job of a given job. The signal for each of the sub-jobs includes information about the respective sub-job and its, priority and requesting job service. Responsive to a first signal, the JCM adds, for a first video capability required by a first sub-job, a corresponding first basic job resource to the queues of each basic resource which the first video capability will require in order to perform the first sub-job. The JCM places the first basic job resources for the first sub-job in an xe2x80x9cActivexe2x80x9d state ready for processing, if the first basic job resources are at the top of all of the queues, of all the basic resources, required by the first video capability. Responsive to a second signal, the JCM adds, for a second video capability required by the second sub-job, a corresponding second basic job resource sub-job to the queues of each basic resource which the second video capability will require in order to perform the first sub-job. The JCM places the second basic job resources, which follow the first basic job resource in a basic resource queue, in an xe2x80x9cActivexe2x80x9d state ready for processing after the first basic job resource, if the first and second basic job resources in the queue are submitted by the same job service and if the second basic job resource is for the same job as the first basic job resource""s sub-job. The basic resources for the first sub-job are placed in an activeDegraded or paused state when the first sub-job is processed and any basic resources which are not used by the second sub-job are released for use by other sub-jobs.
In accordance with another alternative preferred embodiment of the present invention there is provided a method of managing the processing of a plurality of jobs in a multifunctional printing system in which at least one job is inputted for processing at one or more job services. The process comprises providing a controller with a job contention manager (JCM) for prioritizing the printing system""s basic processing resources to enable the JCM to process a job for multiple video capabilities. A plurality of capability resources are provided for carrying out the one or more job services. A plurality of basic resources of the printing system are also provided. Each capability resource contains a list of the basic resources it needs to carry out its capability and each basic resource contains a list of the capability resources that depend upon it. A sub-job queue is provided for each capability resource and each basic resource.
Each respective job service, at a desired time, signals the JCM to carry out a sub-job of said at least one job. The signal for each of the sub-jobs includes information about the respective sub-job and its priority (FIFO or job based priority) and requesting job service. Responsive to a signal, the JCM creates for the at least one sub-job received from the job service, respective capability job resources containing the information, and adds each such capability job resource, based on priority, to the respective capability resource, job queue. Thereafter the JCM adds, for each capability job resource, component basic job resources to the queues of each basic resource which a respective capability resource will require. The JCM places the first basic job resources, which are components of a first capability resource, for the at least one sub-job, in an xe2x80x9cActivexe2x80x9d state ready for processing, if the first basic job resources are at the top of all of the queues, of all the basic resources, required by the first capability resource. The JCM then places the second basic job resources, which are components of a second capability resource, which follow the first basic job resource in a basic resource queue, in an xe2x80x9cActivexe2x80x9d state ready for processing after the first basic job resource, if the first and second basic job resources in the queue are submitted by the same job service and if the second basic job resource is for the same job as the first basic job resource""s sub-job. The basic resources for the first sub-job are placed in an activeDegraded or paused state when the first sub-job is processed and any basic resources which are not used by the second sub-job are released for use by other sub-jobs.
In accordance with another preferred embodiment of this invention an apparatus is provided for prioritizing the use of multifunctional printing system""s basic processing resources. The apparatus employs a controller having a job contention manager (JCM). The apparatus includes: a plurality of basic resources of the printing system with each such resource having a queue; signal means, for one or more job services, at desired times, to signal the JCM to carry out a sub-job of a given job, the signal for each of the sub-jobs including information about the respective job and its job service and priority.
The apparatus further includes means for each respective job service, at a desired time, to send a signal to the JCM to carry out a sub-job of the at least one job, the signal for each of the sub-jobs including information about the respective sub-job and its job service and priority. The JCM includes: means for creating respective capability job resources containing the information, and for adding each such capability job resource, based on priority, to the respective capability resource, job queue; means for adding, for each capability job resource, component basic job resources to the queues of each basic resource which a respective capability resource will require; means for placing first basic job resources, which are components of a first capability resource, for the at least one sub-job, in an xe2x80x9cActivexe2x80x9d state ready for processing, if the first basic job resources are at the top of all of the queues, of all the basic resources, required by the first capability resource; means for placing the second basic job resources, which are components of a second capability resource, and which follow the first basic job resource in a basic resource queue, in an xe2x80x9cActivexe2x80x9d state ready for processing after the first basic job resource, if the first and second basic job resources in the queue are submitted by the same job service and if the second basic job resource is for the same sub as the first basic job resource""s sub-job. Means are provided for placing the basic resources for the first sub-job in an activeDegraded or paused state after the first sub-job is processed as well as means for releasing any basic resources which are not used by the second sub-job for use by other sub-jobs.
An alternative apparatus in accordance with a further preferred embodiment of this invention is provided for managing the processing of a plurality of jobs in a multifunctional printing system in which at least one job is inputted for processing at one or more job services. The apparatus includes a controller having a job contention manager (JCM) for prioritizing the printing system""s basic processing resources. The apparatus comprises: a database which is associated with the JCM. The database includes a plurality of capability resources for carrying out the one or more job services and a plurality of basic resources of the printing system, with each capability resource containing a list of the basic resources it needs to carry out its capability and each basic resource containing a list of the capability resources that depend upon it. The database includes a sub-job queue for each capability resource and each basic resource. Signal means are provided, for permitting each respective job service, at a desired time, to signal the JCM to carry out a sub-job of the at least one job, with the signal for each of the sub-jobs including information about the respective job and its priority and requesting job service.
Each respective job service including means, at a desired time, for sending a signal to the JCM to carry out a sub-job of the at least one job, the signal for each of the sub-jobs including information about the respective sub-job and its job service and priority. The JCM includes: means for creating respective capability job resources containing the information, and adding each such capability job resource, based on priority, to the respective capability resource, job queue; means for adding, for each capability job resource, component basic job resources to the queues of each basic resource which a respective capability resource will require; means for placing first basic job resources, which are components of a first capability resource, for the at least one sub-job, in an xe2x80x9cActivexe2x80x9d state ready for processing, if the first basic job resources are at the top of all of the queues, of all the basic resources, required by the first capability resource; and means for placing second basic job resources, which are components of a second capability resource, which follow the first basic job resource in a basic resource queue, in an xe2x80x9cActivexe2x80x9d state ready for processing after the first basic job resource, if the first and second basic job resources in the queue are submitted by the same job service and if the second basic job resource is for the same job as the first basic job resource""s subjob. Means are provided for placing the basic resources for the first sub-job in an activeDegraded or paused state after the first sub-job is processed as well as means for releasing any basic resources which are not used by the second sub-job for use by other subjobs.
The prioritization approach used by the JCM in the process and apparatus of this invention can be FIFO or a combination of FIFO and job based priority as desired.